package dataStructure.search;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-02 10:34
 */

public class FibonacciSearch {
    public static int fibonacciSize = 20;
    public static int[] fibonacci = new int[fibonacciSize];
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        fibonacci = getFibonacci();
        System.out.println("index下标是 " + search(arr, 134));
        System.out.println("fibonacci数列是 " +
                Arrays.toString(fibonacci));
    }

    //非递归查找
    public static int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int k = 0;  //斐波那契数列下标
        int mid = 0;    //存放中间值

        //要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1。
        //第一步：确定斐波那契数Fibonacci[k]
        while (right > fibonacci[k] - 1) {
            k++;
        }
        System.out.println("k is " + k);

        //f[k]值可能大于数组长度，因此需要拷贝数组
        //不足的部分自动用0填充
        //用arr数组的最后的数填充tempArr
        //temp = {1, 8, 10, 89, 1000, 1234, 0, 0, 0} => temp = {1, 8, 10, 89, 1000, 1234, 1234, 1234, 1234}
        //填充数组方便之后进行分割
        int[] tempArr = Arrays.copyOf(arr, fibonacci[k]);
        System.out.println("拷贝后的tempArr是 " + Arrays.toString(tempArr));
        for (int i = right + 1; i < tempArr.length; i++) {
            tempArr[i] = arr[right];
        }
        System.out.println("填充后的tempArr是 " + Arrays.toString(tempArr));

        int count = 0;
        //while循环查找target
        while (left <= right) {
            mid = left + fibonacci[k - 1] - 1;
            System.out.print("第" + (++count) + "次mid is " + mid);
            if (target == tempArr[mid])  {
                System.out.println(" 找到");
                //因为填充数组的时候，填充的数是数组的最后一个数，因此mid可能大于right
                if (mid <= right) {
                    return mid;
                } else {
                    return right;
                }
            } else if (target < tempArr[mid]) {
                System.out.print(" 向左<- k is " + k);
                //继续向左查找
                right = mid - 1;
                //全部元素(fib[k])=左边的元素(fib[k-1])+右边的元素(fib[k-2])
                //左边有fib[k-1]个数，右边有fibonacci[k-2]个数
                //fib[k-1]=fib[k-2]+fib[k-3]
                k--;
                System.out.println(",change k is " + k);
            } else {
                System.out.print(" 向右-> k is " + k);
                //继续向右查找
                left = mid + 1;
                //fib[k-2]=fib[k-3]+fib[k-4]
                k -= 2;
                System.out.println(",change k is " + k);
            }

        }


        return -1;
    }

    //非递归获取斐波那契数列
    private static int[] getFibonacci() {
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        for (int i = 2; i < fibonacciSize; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }
}
